public class MyLinkList implements lList {
    ListNode headnode = null;

    public void addFirst(int data) {
        if (headnode == null) {
            this.headnode = new ListNode(data);
        } else {
            ListNode newnode = new ListNode(data);
            newnode.next = headnode;
            newnode.next.prev = newnode;
            this.headnode = newnode;
        }
    }

    public void addLast(int data) {
        if (headnode == null) {
            this.headnode = new ListNode(data);
        } else {
            ListNode node = this.headnode;
            while (node.next != null) {
                node = node.next;
            }

            //定位到最后一个节点
            ListNode newnode = new ListNode(data);
            node.next = newnode;
            newnode.prev = node;
        }
    }
    //任意位置插入,第一个数据节点为0号下标

    public void addIndex(int index, int data) {

        if (index == 0) {
            addFirst(data);
            return;
        } else if (index == this.size() - 1) {
            addLast(data);
            return;
        }

        ListNode node = this.headnode;
        int index1 = index - 1;
        while (index1 > 0) {
            node = node.next;
            index1--;
        }

        ListNode newnode = new ListNode(data);

        //新增节点的前后驱信息
        newnode.next = node.next;
        newnode.prev = node;

        //新增节点的后一个节点的前驱信息
        node.next.prev = newnode;

        //新增节点的前一个节点的后驱信息
        node.next = newnode;

    }

    public boolean contains(int key) {
        ListNode node = this.headnode;
        while (node != null) {
            if (node.value == key) {
                return true;
            } else node = node.next;
        }
        return false;
    }

    public void remove(int key) {
        if (this.headnode.next == null && this.headnode.prev == null)
            headnode = null;

        ListNode node = this.headnode;
        while (node != null) {        //找到要删除的节点
            if (node.value == key) {
                if (node.prev == null) {  //删除头节点
                    node.next.prev = null;
                    this.headnode = node.next;
                    node.next = null;
                    return;
                } else if (node.next == null) {  //删除尾节点
                    node.prev.next = null;
                    node.prev = null;
                    return;
                } else {  //删除中间节点
                    node.prev.next = node.next;
                    node.next.prev = node.prev;
                    node.prev = null;
                    node.next = null;
                    return;
                }
            }
            node = node.next;
        }
    }

    public void removeAllKey(int key) {
        ListNode node = this.headnode;
        int num = 0;
        while (node != null) {
            if (node.value == key)
                num++;
            node = node.next;
        }

        while (num > 0) {
            this.remove(3);
            num--;
        }
    }

    public int size() {
        int num = 0;
        ListNode node = this.headnode;
        while (node != null) {
            node = node.next;
            num++;
        }
        return num;
    }

    public void clear() {
        if (this.headnode == null)
            return;

        ListNode node = this.headnode.next;
        while (true) {
            if (this.headnode.next != null) {
                this.headnode.prev = null;
                this.headnode = node;
            } else {
                this.headnode.prev = null;
                this.headnode = null;
                break;
            }
        }
    }

    public void display() {
        ListNode node = this.headnode;
        while (node != null) {
            System.out.println(node.value);
            node = node.next;
        }
    }

    static public class ListNode {
        int value;
        ListNode next = null; //大写N代表当前节点的下一个节点
        ListNode prev = null;

        public ListNode(int value) {
            this.value = value;
        }
    }
}
